//从底部向上进行处理，从最后一个带子节点的节点开始进行sink操作（也就是N/2开始），一直到根节点
//然后只需反复进行delmax，就可以得到从大到小的数组顺序
//堆排序是可以保证nlogn时间复杂度的就地排序算法
//因为没有用到缓存，所以速度没有快速排序更快
//因为算法不是稳定的，所以可能会选择归并排序
public class HeapSort extends Sort{
    int size;       //返回有效的储存元素  新元素就插在size的位置
    int maxN;       //返回存储空间
    public void MySort(int data[])
    {
       maxN=data.length;
       size=data.length;
       int k=maxN/2;
       while (k>=0) {
        sink(data,k);
        k--;
       }
       for(int i=0;i<data.length;i++)
       {
        DelMax(data);
       }
    }

    public void swim(int data[],int k)
  {
     while(true)
     {
        if(k<=0)
        {
            break;
        }
        else
        {
            if(data[k]>data[k/2])
            {
                Exchange(data,k,k/2);
                k/=2;
            }
            else
            {
                break;
            }
        }
     }
  }   

  public void sink(int data[],int k)
  {
    k++;                       //k是逻辑上的位置
    while(true)
    {
     int j=2*k;                //找到逻辑上k子结点的编号
     if(j>size)                //j-1是物理上子结点的位置 j-1需要小于或等于size-1，因为size代表最后一个元素再后一个的偏移量
     {
        return;
     }
     if(j<=size-1&&data[j-1]<data[j])   //如果逻辑上j+1的位置在物理上存在，并且还大于j对应的节点
     {
        j++;
     }
     
     if(data[k-1]<data[j-1])
     {
        Exchange(data,k-1,j-1);
        k=j;
     }
     else
     {
        return;
     }
    }
  }

  public int DelMax(int data[])
  {
     int max=data[0];
     Exchange(data,0,size-1);
     size--;
     sink(data,0);
     return max;
  }
}
